// https://leetcode.cn/problems/number-of-islands/
// Created by ade on 2022/8/25.
//
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

class Solution {
public:
    vector <vector<int>> vi;
    int row = 0;
    int col = 0;
    int numIslands(vector<vector<char>>& grid) {
        row = grid.size();
        col = grid[0].size();
        int num = 0;

        vi.resize(row, vector<int>(col));
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (vi[i][j] == 1) continue;
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    num++;
                }
            }
        }
        return num;
    }

    void dfs(vector<vector<char>>& grid, int i, int j){
        if(i < 0 || j < 0 || i >= row || j >= col || vi[i][j] == 1 || grid[i][j] == '0') return;
        vi[i][j] = 1;
        dfs(grid, i + 1,j);
        dfs(grid, i - 1,j);
        dfs(grid, i ,j + 1);
        dfs(grid, i ,j - 1);
    }
};


int main() {
    Solution so;
    vector <vector<char >> grid = {
            {'1', '1', '1', '1', '0'},
            {'1', '1', '0', '1', '0'},
            {'1', '1', '0', '0', '0'},
            {'0', '0', '0', '0', '0'}
    };
    auto res = so.numIslands(grid);
    cout << res << endl;
    return 0;
}